package sort;

public class AshSort {
	public static long Sort(int[] list){
		long startTime = System.currentTimeMillis();
		
		//for(int i=0; i<list.length; i++) System.out.print(list[i] + " ");
		
		int[] estimateArray = new int[2 * list.length];
		//Initialising all elements to -1 so that we can tell later on
		//if the entry is "empty" (negative).
		for(int i=0; i<estimateArray.length; i++){
			estimateArray[i] = -1;
		}		
		
		//Estimate the position of the (normally distributed) list,
		//and if there is something already there then put it elsewhere.
		//(this assumes that the max number = range)<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
		for(int i=0; i<list.length; i++){
			if(estimateArray[list[i]] == -1){
				estimateArray[list[i]] = list[i];
			}
			else{
				int countBack = list[i]-1, countForward = list[i]+1;
				while(true){
					boolean keepGoingBackIndex = true, keepGoingForwardIndex = true;
					if(countBack < 0){
						keepGoingBackIndex = false;
					}
					if(countForward >= estimateArray.length){
						keepGoingForwardIndex = false;
					}
					
					if(keepGoingBackIndex == false && keepGoingForwardIndex == false){
						System.out.println("there are no more spaces in the array......(error?)");
						break;
					}
					else if(keepGoingBackIndex == true){
						if(estimateArray[countBack] == -1){
							estimateArray[countBack] = list[i];
							//System.out.println("broken backward");
							break;							
						}
						countBack--;
					}
					else if(keepGoingForwardIndex == true){
						if(estimateArray[countForward] == -1){
							estimateArray[countForward] = list[i];
							//System.out.println("broken forward");
							break;							
						}
						countForward++;
					}
					else{//ERROR
						System.out.println("#wtfCrazyError: Neither else if statement is entered");
						System.out.println("countBack = " + countBack);
						System.out.println("countForward = " + countForward);
						System.out.println("list[i]-countBack = " + (list[i]-countBack));
						System.out.println("countForward-list[i] = " + (countForward-list[i]));
						System.out.println("keepGoingBackIndex = " + keepGoingBackIndex);
						System.out.println("keepGoingForwardIndex = " + keepGoingForwardIndex);
					}
				}
			}
		}
		
		//System.out.println();
		//for(int i=0; i<estimateArray.length; i++) System.out.print(estimateArray[i] + " ");

		
		//Bubble sort
		for(int i=0; i < estimateArray.length -1; i++){
			int temp;   //holding variable for estimateArray[j]
		    for(int j=0; j < estimateArray.length -1; j++){
		    	//No point sorting if either j or j+1 are -1.
		    	if ((estimateArray[j] > estimateArray[j+1]) && !(estimateArray[j] == -1 || estimateArray[j+1] == -1)){
		    		temp = estimateArray[j];
		    		estimateArray[j] = estimateArray[j+1];
		    		estimateArray[j+1] = temp;
		    	}
		    }
		}
		    
	    //Final sort of "list" based on "estimateArray".
	    for(int i=0, j=0; i < list.length; i++, j++){
	    	while(estimateArray[j] == -1){
	    		j++;
	    	}
		    list[i] = estimateArray[j];
	    }
	    
	    //System.out.println();
		//for(int i=0; i<list.length; i++) System.out.print(list[i] + " ");

		
		return (System.currentTimeMillis()-startTime);
	}
}
